package org.basis.algorithm.promote;

import java.util.List;

/**
 * 派对最大快乐值问题
 *
 * @author Mr_wenpan@163.com 2022/01/12 22:27
 */
public class MaxHappy {

    public static void main(String[] args) {

    }

    public static int maxHappy(Employee boss) {
        if (boss == null) {
            return 0;
        }
        Info info = process(boss);
        return Math.max(info.laiMaxHappy, info.buLaiMaxHappy);
    }

    public static Info process(Employee employee) {

        // base case
        if (employee.subordinates == null) {
            return new Info(employee.happy, 0);
        }
        // 当前员工来的快乐值
        int lai = employee.happy;
        // 当前员工不来的快乐值
        int buLai = 0;
        // 获取到所有直接下级员工的信息
        for (Employee subordinate : employee.subordinates) {
            Info process = process(subordinate);
            // 当前员工来了，那么他的直接下级就不能来
            lai += process.buLaiMaxHappy;
            // 如果当前员工不来，那么他不来的最大值就是他下面的所有直接员工来或者不来的最大值之和
            buLai = Math.max(process.buLaiMaxHappy, process.laiMaxHappy);
        }

        // 整合信息向上返回
        return new Info(lai, buLai);
    }

    static class Info {
        int laiMaxHappy;
        int buLaiMaxHappy;

        public Info(int laiMaxHappy, int buLaiMaxHappy) {
            this.laiMaxHappy = laiMaxHappy;
            this.buLaiMaxHappy = buLaiMaxHappy;
        }
    }

    static class Employee {
        // 这名员工可以带来的快乐值
        public int happy;
        // 这名员工有哪些直接下级
        List<Employee> subordinates;

        public Employee() {

        }

    }

}
